/**
 * 两个条件：
 * 1. 奇偶数位数量相等
 * 2. K的倍数
 * 
 * 因为在1E9以内，K在20以内，因此定义
 * D[10][20][20]
 * Dijk，其中j表示对K的余数，k表示奇偶之差加10
 */
using llt = long long;
int Beishu;
vector<int> G;
// Dijk, j表示余数，k表示奇偶之差加10
llt D[10][20][20];
llt dfs(int pos, int r, int cha, bool lead, bool limit){
    if(-1 == pos) {
        if(lead or r or cha != 10) return 0;// 纯0不能算
        return 1;
    }
    if(not lead and not limit and -1 != D[pos][r][cha]) {
        return D[pos][r][cha];
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(0 == i and lead){ // 前导0不能计算差
            ans += dfs(pos - 1, 0, 10, true, limit&&last==i);
        }else{
            int ncha = (i & 1) ? cha + 1 : cha - 1;
            int nr = (r * 10 + i) % Beishu;
            ans += dfs(pos - 1, nr, ncha, false, limit&&last==i);            
        }
    }
    if(not lead and not limit){
        D[pos][r][cha] = ans;
    }    
    return ans;
}

llt digitDP(int n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    return dfs(G.size()-1, 0, 10, true, true);
}

class Solution {
public:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        memset(D, -1, sizeof(D));
        Beishu = k;
        auto t1 = digitDP(low - 1);
        auto t2 = digitDP(high);
        return t2 - t1;
    }
};